/* Copyright (C) 2007 Free Software Foundation, Inc.
 * See the copyright notice in the file /usr/LICENSE.
 * Created by flyan on 2020/6/11.
 * QQ: 1341662010
 * QQ-Group:909830414
 * gitee: https://gitee.com/flyanh/
 *
 * 739. 每日温度
 * 根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
 *
 * 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
 *
 * 提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
 */
#include <iostream>
#include <sstream>
#include <cstring>
#include <cassert>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <stack>

using namespace std;

class Solution {
public:
    /* 真正的暴力搜，但是超时了，真遗憾，时间复杂度 O(nm)，m 会递减，但也很高 */
//    static vector<int> dailyTemperatures(const vector<int>& T) {
//        int t_size = T.size();
//        vector<int> ans(t_size, 0);
//        for(int i = 0; i < t_size - 1; ++i) {
//            int curr_t = T[i];
//            for(int j = i + 1, step = 1; j < t_size; ++j, ++step) {
//                if(T[j] > curr_t) {
//                    ans[i] = step;
//                    break;
//                }
//            }
//        }
//        return ans;
//    }

    /* 利用栈来达到时间复杂度 O(n)，只需要遍历一遍即可 */
    static vector<int> dailyTemperatures(const vector<int>& T) {
        int t_size = T.size();
        vector<int> ans(t_size, 0);
        stack<int> S;
        for(int i = 0; i < t_size; ++i) {
            int top;
            while ( !S.empty() ) {
                if(T[i] > T[( top = S.top() )]) {
                    S.pop();
                    ans[top] = i - top;
                } else break;
            }
            S.push(i);
        }
        return ans;
    }
};

int main() {
    vector<int> in = { 55,38,53,81,61,93,97,32,43,78 };
    vector<int> ans = Solution::dailyTemperatures(in);
    for(const int i : ans) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}
